package net.tp.algo.text;

import net.tp.algo.graph.Traversal;
import net.tp.util.Wrappers;

import java.util.*;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * <p>Suffix Tree.</p>
 *
 * <p>Suffix Tree of string S is a compressed trie of all suffixes of S.</p>
 *
 * <p>Normally, we usually append a sentinel character $ to a string before building the suffix tree, assuming that $ does not
 * appear anywhere in the string. This is to make sure each suffix ends in its own leaf ⇒ the number of leaves =
 * the number of suffixes.</p>
 *
 * <p>Applications:</p>
 * <ul>
 *     <li>Search for all occurrences of pattern P in string S.</li>
 *     <li>Find the longest repeated substring</li>
 *     <li>Compare 2 substrings (given 2 index) to find the longest common prefix, using LCA.</li>
 *     <li>Find all occurrences of T[i:j], using Level Ancestor</li>
 *     <li>Multiple documents</li>
 *     <li>Document retrieval problem: find the number of documents that match a pattern P, using RMQ.</li>
 * </ul>
 *
 * @author Trung Phan
 *
 * @see <a href="http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm">Suffix tree</a>
 * @see <a href="http://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english">Suffix tree explained at Stack Overflow</a>
 */
public class SuffixTree {
	
	private final String text;
	
	private final Node root;
	
	private static final Logger logger = Logger.getLogger(SuffixTree.class.getName());
	
	public static boolean SHOW_EDGE_START = false;
	
	public SuffixTree(String text) {
		this.text = text;
		this.root = buildSuffixTree(text);
	}
	
	public int search(String pattern) {
		if (pattern.length() == 0) {
			return 0;
		}
		
		Edge edge = root.edges.get(pattern.charAt(0));
		if (edge == null) {
			return -1;
		}
		int foundPosition = edge.start;		
		
		int activePosition = edge.start;
		for (int i = 0; i < pattern.length(); i++) {
			char cp = pattern.charAt(i);
			if (activePosition >= edge.end) {
				if (edge.nextNode == null) {
					return -1; // reach the end of the string
				}
				edge = edge.nextNode.edges.get(cp);
				if (edge == null) {
					return -1;
				}
				
				activePosition = edge.start;
				foundPosition = activePosition - i;
			}

			char ct = text.charAt(activePosition);
			if (cp != ct) {
				return -1;
			}
			activePosition++;
		}
		
		return foundPosition;
	}
	
	/**
	 * 
	 * 
	 * <p>Ukkonen's algoirthm to build Suffix Tree.</p>
	 * 
	 * <p>The algorithm utilizes some key variables to make sure running time to be $O(n)$:</p>
     * <ul>
     *     <li><strong>Remainder.</strong> Remainder is one of the most important variables to understand the algorithm.
     *     Remainder keeps track of how many suffixes to process. The remainder is incremented
     *     at the beginning of each iteration to indicate that the current character needs to be added to the tree.
     *     If the current character is added to the tree, the remainder is decremented to 0; otherwise, it will keep incrementing.
     *     For example, for a text {@code abcabdabcx}:
     *     <pre>
     *         initial: active point = (root, '', 0)
     *
     *         i   char    actions
     *         0   a       remainder++ to 1,    a does not exist, add    a to the tree, remainder-- to 0.
     *         1   b       remainder++ to 1,    b does not exist, add    b to the tree, remainder-- to 0.
     *         2   c       remainder++ to 1,    c does not exist, add    c to the tree, remainder-- to 0.
     *         3   a       remainder++ to 1,    a already exists,                                         active point := (root , 'a', 1)
     *         4   b       remainder++ to 2,   ab already exists,                                         active point := (root , 'a', 2)
     *         5   d       remainder++ to 3,  abd does not exist, add  abd to the tree, remainder-- to 2, active point := (root , 'b', 1)
     *                                                            add   bd to the tree, remainder-- to 1, active point := (root , '' , 0)
     *                                                            add    d to the tree, remainder-- to 0.
     *         6   a       remainder++ to 1,    a already exists,                                         active point := (root , 'a', 1)
     *         7   b       remainder++ to 2,   ab already exists,                                         active point := (node1, '' , 0)
     *         8   c       remainder++ to 3,  abc already exists,                                         active point := (node1, 'c', 1)
     *         9   x       remainder++ to 4, abcx does not exist, add abcx to the tree, remainder-- to 3, active point := (node2, 'c', 1)
     *                                                            add  bcx to the tree, remainder-- to 2, active point := (root , 'c', 1)
     *                                                            add   cx to the tree, remainder-- to 1, active point := (root , '' , 0)
     *                                                            add    x to the tree, remainder-- to 0.
     *
     *     </pre></li>
     *     <li><strong>Active Node, Active Edge, Active Length.</strong> Active node, edge and length combined are the active
     *     point to determine where to insert new character for the new suffix. It also determines if the current suffix already exists.
     *     In the above example, in iteration 3, 4, these variables help to determine that ab suffix already exists in the tree.</li>
     *     <li><strong>Active Node.</strong> Active node is never null (until the algorithm is finished).</li>
     *     <li><strong>Active Edge.</strong> Active edge is char instead of the Edge object. To get the real Edge object, invoke activeNode.edge(activeEdge).
     *     The reason for using char instead of Edge object is because Edge object can change (when activeNode is
     *     changed) even though activeEdge char does not change.</li>
     *     <li><strong>Suffix Link.</strong> Suffix link is used to quickly locate where to insert new node or new character.
     *     In the above example, suppose we add abcx to the tree. It's easy to add abcx because the active node, edge
     *     and length tell us where abc is. Next we need to add bcx, this is when suffix link will help to locate
     *     quickly where bc is to add bcx into the tree.</li>
     * </ul>
     *
     * <p>To quickly find out if a suffix is already exist in a tree, and to quickly find out where to insert new
     * character into the tree, these rules need to be followed:</p>
     * <ul>
     *     <li><strong>Rule 1.</strong> After an edge is split and the active node is the root, keep active node at the root,
     *     set active edge to the first character of the new suffix, decrement active length by 1. Look at iteration 5,
     *     where we need to add abd to the tree. At this moment, the active point (active node = root, active edge = 'a',
     *     active length = 2) tells us where to add new edge for d (by splitting the current edge abc...).
     * <pre>
     *      <span style='color:red'>╤ ab</span> cabd?
     *      │   <span style='color:Gainsboro'>└───────────────────────────────</span> active point
     *      ├ bcabd?
     *      └ cabd?
     * </pre>
     *     Once d is inserted (i.e. suffix abd is added), the next suffix to add is bd. According to rule 1,
     *     the new active point becomes (active node = root, active edge = 'b', active length decremented to 1). This new
     *     active point tells us where to insert the d for the suffix bd:
     * <pre>
     *      <span style='color:red'>╤</span> ab ┬ cabd?
     *      │    └ d?
     *      ├ <span style='color:red'>b</span> cabd?
     *      │  <span style='color:Gainsboro'>└────────────────────────────────</span> active point
     *      └ cabd?
     * </pre>
     *     Once d is inserted for suffix bd, the next suffix to add is d. According to rule 1, new new active point
     *     becomes (active node = root, active edge = empty, active length decremented to 0).
     * <pre>
     *      <span style='color:red'>╤</span> ab ┬ cabd?
     *      │    └ d?
     *      ├ b ┬ cabd?
     *      │   └ d?
     *      └ cabd?
     *      <span style='color:Gainsboro'>└───────────────────────────────────</span> active point
     * </pre>
     *     To insert the d, we need to create new edge (instead of splitting the edge as above) because active length = 0.
     * <pre>
     *      <span style='color:red'>╤</span> ab ┬ cabd?
     *      │    └ d?
     *      ├ b ┬ cabd?
     *      │   └ d?
     *      ├ cabd?
     *      └ d?
     * </pre>
     *     </li>
     *     <li><strong>Rule 2.</strong> Within an iteration, when we create new nodes (by splitting edges), we link those
     *     new nodes through special suffix link: the previously created node will link to the newly created node.
     * <pre>
     *      <span style='color:red'>╤</span> ab ↓┬ cabd?
     *      │    <span style='color:red'>┆</span>└ d?
     *      │   <span style='color:red'>╭╯</span>
     *      │   <span style='color:red'>┆</span>
     *      ├ b ∘┬ cabd?
     *      │    └ d?
     *      ├ cabd?
     *      └ d?
     * </pre>
     *     </li>
     *     <li><strong>Rule 3.</strong> After an edge is split and the active node is not the root,
     *     if suffix link of active node is not null, set the active node = suffix link, active edge and length remains unchanged.
     *     If the suffix link is null, set active node = root.
     * <pre>
     *      ┬ ab ↓<span style='color:red'>╤ c</span> abdabcx?
     *      │     │  <span style='color:Gainsboro'>└──────────────────────────</span> active point
     *      │     └ dabcx?
     *      ├ b ∘┬ cabdabcx?
     *      │    └ dabcx?
     *      ├ cabdabcx?
     *      └ dabcx?
     * </pre>
     *
     * <pre>
     *      ┬ ab ↓┬ c ┬ abdabcx?
     *      │     │   └ x
     *      │     └ dabcx?
     *      ├ b ∘<span style='color:red'>╤ c</span> abdabcx?
     *      │    │  <span style='color:Gainsboro'>└───────────────────────────</span> active point
     *      │    └ dabcx?
     *      ├ cabdabcx?
     *      └ dabcx?
     * </pre>
     *
     * <pre>
     *      <span style='color:red'>╤</span> ab ↓┬ c ↓┬ abdabcx?
     *      │     │    └ x
     *      │     └ dabcx?
     *      ├ b ∘┬ c ∘┬ abdabcx?
     *      │    │    └ x
     *      │    └ dabcx?
     *      ├ <span style='color:red'>c</span> abdabcx?
     *      │  <span style='color:Gainsboro'>└────────────────────────────────</span> active point
     *      └ dabcx?
     * </pre>
     *
     * <pre>
     *      <span style='color:red'>╤</span> ab ↓┬ c ↓┬ abdabcx?
     *      │     │    └ x
     *      │     └ dabcx?
     *      ├ b ∘┬ c ↧┬ abdabcx?
     *      │    │    └ x
     *      │    └ dabcx?
     *      ├ c ∘┬ abdabcx?
     *      │    └ x
     *      └ dabcx?
     *      <span style='color:Gainsboro'>└───────────────────────────────────</span> active point (rule 1)
     * </pre>
     *     </li>
     * </ul>
	 *
     * <p>Some other minor rules:</p>
     * <ul>
     *     <li><strong>Walk down the edge.</strong> When active length ≥ active edge's length, the active node
     *     must keep moving to the next node until active length &lt; active edge's length. This happens when active point
     *     moves forward (i.e. active length incremented), or active point move to a different node through suffix
     *     link.</li>
     * </ul>
     *
     *
	 * <p>Complete steps to build suffix tree for text {@code abcabdabcx}<p>
	 *
	 * <pre>
	 *
     * 0.
     * <span style='color:red'>a</span>bcabdabcx  ⇒  abcabdabcx :
     *      <span style='color:red'>═</span> a?
     *
     * 1.
     * a<span style='color:red'>b</span>cabdabcx  ⇒  abcabdabcx :
     *      <span style='color:red'>╤</span> ab?
     *      └ b?
     *
     * 2.
     * ab<span style='color:red'>c</span>abdabcx  ⇒  abcabdabcx :
     *      <span style='color:red'>╤</span> abc?
     *      ├ bc?
     *      └ c?
     *
     * 3.
     * abc<span style='color:red'>a</span>bdabcx  ⇒  abc<span style='color:red'>a</span>bdabcx :
     *      <span style='color:red'>╤</span> <span style='color:red'>a</span>bca?
     *      ├ bca?
     *      └ ca?
     *
     * 4*.
     * abc<span style='color:red'>ab</span>dabcx  ⇒  abc<span style='color:red'>ab</span>dabcx :
     *      <span style='color:red'>╤</span> <span style='color:red'>ab</span>cab?
     *      ├ bcab?
     *      └ cab?
     *
     * 5*.
     * abc<span style='color:red'>abd</span>abcx  ⇒  abca<span style='color:red'>bd</span>abcx :
     *      <span style='color:red'>╤</span> ab ┬ cabd?
     *      │    └ d?
     *      ├ <span style='color:red'>b</span>cabd?
     *      └ cabd?
     *
     * 5*.
     * abca<span style='color:red'>bd</span>abcx  ⇒  abcab<span style='color:red'>d</span>abcx :
     *      <span style='color:red'>╤</span> ab ↓┬ cabd?
     *      │     └ d?
     *      ├ b ∘┬ cabd?
     *      │    └ d?
     *      └ cabd?
     *
     * 5.
     * abcab<span style='color:red'>d</span>abcx  ⇒  abcabdabcx :
     *      <span style='color:red'>╤</span> ab ↓┬ cabd?
     *      │     └ d?
     *      ├ b ∘┬ cabd?
     *      │    └ d?
     *      ├ cabd?
     *      └ d?
     *
     * 6.
     * abcabd<span style='color:red'>a</span>bcx  ⇒  abcabd<span style='color:red'>a</span>bcx :
     *      <span style='color:red'>╤</span> <span style='color:red'>a</span>b ↓┬ cabda?
     *      │       └ da?
     *      ├ b ∘┬ cabda?
     *      │    └ da?
     *      ├ cabda?
     *      └ da?
     *
     * 7*.
     * abcabd<span style='color:red'>ab</span>cx  ⇒  abcabd<span style='color:red'>ab</span>cx :
     *      ┬ ab ↓<span style='color:red'>╤</span> cabdab?
     *      │     └ dab?
     *      ├ b ∘┬ cabdab?
     *      │    └ dab?
     *      ├ cabdab?
     *      └ dab?
     *
     * 8*.
     * abcabd<span style='color:red'>abc</span>x  ⇒  abcabd<span style='color:red'>abc</span>x :
     *      ┬ ab ↓<span style='color:red'>╤</span> <span style='color:red'>c</span>abdabc?
     *      │     └ dabc?
     *      ├ b ∘┬ cabdabc?
     *      │    └ dabc?
     *      ├ cabdabc?
     *      └ dabc?
     *
     * 9*.
     * abcabd<span style='color:red'>abcx</span>  ⇒  abcabda<span style='color:red'>bcx</span> :
     *      ┬ ab ↓┬ c ┬ abdabcx
     *      │     │   └ x
     *      │     └ dabcx
     *      ├ b ∘<span style='color:red'>╤</span> <span style='color:red'>c</span>abdabcx
     *      │    └ dabcx
     *      ├ cabdabcx
     *      └ dabcx
     *
     * 9*.
     * abcabda<span style='color:red'>bcx</span>  ⇒  abcabdab<span style='color:red'>cx</span> :
     *      <span style='color:red'>╤</span> ab ↓┬ c ↓┬ abdabcx
     *      │     │    └ x
     *      │     └ dabcx
     *      ├ b ∘┬ c ∘┬ abdabcx
     *      │    │    └ x
     *      │    └ dabcx
     *      ├ <span style='color:red'>c</span>abdabcx
     *      └ dabcx
     *
     * 9*.
     * abcabdab<span style='color:red'>cx</span>  ⇒  abcabdabc<span style='color:red'>x</span> :
     *      <span style='color:red'>╤</span> ab ↓┬ c ↓┬ abdabcx
     *      │     │    └ x
     *      │     └ dabcx
     *      ├ b ∘┬ c ↧┬ abdabcx
     *      │    │    └ x
     *      │    └ dabcx
     *      ├ c ∘┬ abdabcx
     *      │    └ x
     *      └ dabcx
     *
     * 9.
     * abcabdabc<span style='color:red'>x</span>  ⇒  abcabdabcx :
     *      <span style='color:red'>╤</span> ab ↓┬ c ↓┬ abdabcx
     *      │     │    └ x
     *      │     └ dabcx
     *      ├ b ∘┬ c ↧┬ abdabcx
     *      │    │    └ x
     *      │    └ dabcx
     *      ├ c ∘┬ abdabcx
     *      │    └ x
     *      ├ dabcx
     *      └ x
     *
	 * </pre>
	 * 
	 * 
	 * @param text text to build suffix tree
	 * @return suffix tree root
	 */
	public final static Node buildSuffixTree(String text) {
		
		logEntering();
		
		Node root = new Node(text, null, 0);
        ActivePoint ap = new ActivePoint(root, '\0', 0);
		int remainder = 0;
		
		for (int i = 0; i < text.length(); i++) {
			char c = text.charAt(i);
			remainder++;
			Node prevNode = null;
			
			for ( ;remainder > 0; remainder--) {

				// the code for walking down the edge can be put here, instead of the 2 places below, but it's harder to read.

				logStepBegin(root, i, remainder);

				assert invariant(ap, i);
				
				if (ap.exists(c)) {
					if (ap.activeEdge == '\0') ap.activeEdge = c;
					ap.activeLength++;

                    if (prevNode != null) prevNode.suffixLink = ap.activeNode; // rule 2

                    ap.walkDownTheEdge(i);

					logStepEnd(root, ap, i, remainder);
					
					break;
				}

                Node nextNode;
				if (ap.activeEdge == '\0') {
					ap.activeNode.addNewEdge(c, i);
                    nextNode = ap.activeNode;
				}
				else {
					Edge newEdge = ap.activeNode.edge(ap.activeEdge).split(ap.activeLength, c, i);
                    nextNode = newEdge.parentNode;
				}

                if (prevNode != null) prevNode.suffixLink = nextNode; // rule 2
                prevNode = nextNode;

				if (ap.activeNode != root) { // rule 3
					ap.activeNode = ap.activeNode.suffixLink != null ? ap.activeNode.suffixLink : root;
				}
				else if (ap.activeLength > 0) { // rule 1
					ap.activeLength--;
					ap.activeEdge = ap.activeLength == 0 ? '\0' : text.charAt(i - ap.activeLength);
				}

                ap.walkDownTheEdge(i);

				logStepEnd(root, ap, i, remainder-1);
				
			}
		}


        sortEdges(root);

		logExiting();
		
		return root;
	}

    /**
     * Populate node.sortedEdges for each node.
     * @param root suffix tree root
     */
    private static void sortEdges(Node root) {
        List<Node> nodes = Traversal.bsf(root, (n) -> n.children(), new HashSet<>());

        int R = 0;
        for (int i = 0; i < root.text.length(); i++) {
            char c = root.text.charAt(i);
            if (R < c) R = c;
        }

        BitSet bitSet = new BitSet(R+1);

        for (Node n : nodes) {
            assert n.edges != null;

            n.sortedEdges = new char[n.edges.size()];
            for (Character c : n.edges.keySet()) {
                bitSet.set(c);
            }
            for (int i = 0, c = bitSet.nextSetBit(0); c >= 0; c = bitSet.nextSetBit(c+1), i++) {
                bitSet.clear(c);
                n.sortedEdges[i] = (char)c;
            }
        }
    }

    /**
	 * Invariants: activeNode is never null. ActiveLength must be less than active edge's length.
	 * 
	 * @param ap active point
	 * @return true if invariant check is successful
	 */
	private static boolean invariant(ActivePoint ap, int i) {
		
		String text = ap.activeNode.text;
		
		if (ap.activeNode == null || ap.activeLength < 0 || ap.activeLength > text.length()) {
			return false;
		}
		
		if ((ap.activeEdge == '\0' && ap.activeLength != 0) || (ap.activeEdge != '\0' && ap.activeLength == 0)) {
			return false;
		}
		
		if (ap.activeEdge != '\0') {
			Edge edge = ap.activeNode.edge(ap.activeEdge);
			if (edge == null) {
				return false;
			}
			
			if (ap.activeLength >= edge.length()) {
				return false;
			}
			
			if (ap.activeEdge != text.charAt(i - ap.activeLength)) {
				return false;
			}
		}
		
		return true;
	}
	
	private static StringBuilder logBuilder;
	
	private static void logEntering() {
		if (logger.isLoggable(Level.FINE)) {
			logBuilder = new StringBuilder();
		}
	}
	
	private static void logStepBegin(Node root, int step, int remainder) {
		if (logger.isLoggable(Level.FINE)) {
			logBuilder.append(String.format("%d%s.\n", step, remainder > 1 ? "*" : ""));
			logBuilder.append(logText(root.text, step, remainder));
		}
	}
	
	private static void logStepEnd(Node root, ActivePoint ap, int step, int remainder) {
		if (logger.isLoggable(Level.FINE)) {
			logBuilder.append("  ⇒  ").append(logText(root.text, step, remainder)).append(" :\n     ");
			root.toString(5, logBuilder, ap, step);
			logBuilder.append('\n');
		}
	}

    private static void logStep(Node root, String suffix, ActivePoint ap, int step) {
        if (logger.isLoggable(Level.FINE)) {
            logBuilder.append(step).append(". Add suffix ").append(suffix).append(":\n     ");
            root.toString(5, logBuilder, ap, root.text.length());
            logBuilder.append('\n');
        }
    }

	private static void logExiting() {
		if (logger.isLoggable(Level.FINE)) {
			String log = logBuilder.toString();


            // uncomment this code to colorize tree
			//log = log.replaceAll("\\[([^]]*)\\]", "<span style='color:red'>$1</span>")
			//		.replaceAll("([═╤])", "<span style='color:red'>$1</span>");

			logger.fine(log);
			logBuilder = null;
		}
	}

	private static String logText(String text, int step, int remainder) {
		StringBuilder builder = new StringBuilder();
		for (int i = 0; i < text.length(); i++) {
			if (remainder > 0 && i == step + 1 - remainder) builder.append('[');
			builder.append(text.charAt(i));
			if (i == step && remainder > 0) builder.append(']');
		}
		return builder.toString();
	}


    /**
     * <p>Build suffix tree from suffix array and lcp array.</p>
     *
     * <p>From suffix tree, one can build suffix array and lcp array by traversing dfs in lexical order. To build
     * suffix tree from suffix array and lcp array is like reconstructing the dfs in lexical order. Basically,
     * the suffixes are added in the order of suffix array. For the first suffix, the first edge is added to the
     * root node. To determine where to insert the edge for the next suffix in the suffix array, consider the
     * longest common prefix of the current suffix with the previous suffix. That will determine where to split
     * to produce a new edge for the next suffix.</p>
     *
     * <p>Example of building suffix tree for text {@code banana¥}:</p>
     * <pre>
     * i  SA LCP S
     * ─  ── ─── ───────
     * 0  6  0   ¥
     * 1  5  0   a¥
     * 2  3  1   ana¥
     * 3  1  3   anana¥
     * 4  0  0   banana¥
     * 5  4  0   na¥
     * 6  2  2   nana¥
     *
     * 0. Add suffix ¥:
     *      <span style='color:red'>═</span> <span style='color:red'>¥</span>
     *
     * 1. Add suffix a¥:
     *      <span style='color:red'>╤</span> ¥
     *      └ <span style='color:red'>a¥</span>
     *
     * 2. Add suffix ana¥:
     *      ┬ ¥
     *      └ a <span style='color:red'>╤</span> ¥
     *          └ <span style='color:red'>na¥</span>
     *
     * 3. Add suffix anana¥:
     *      ┬ ¥
     *      └ a ┬ ¥
     *          └ na <span style='color:red'>╤</span> ¥
     *               └ <span style='color:red'>na¥</span>
     *
     * 4. Add suffix banana¥:
     *      <span style='color:red'>╤</span> ¥
     *      ├ a ┬ ¥
     *      │   └ na ┬ ¥
     *      │        └ na¥
     *      └ <span style='color:red'>banana¥</span>
     *
     * 5. Add suffix na¥:
     *      <span style='color:red'>╤</span> ¥
     *      ├ a ┬ ¥
     *      │   └ na ┬ ¥
     *      │        └ na¥
     *      ├ banana¥
     *      └ <span style='color:red'>na¥</span>
     *
     * 6. Add suffix nana¥:
     *      ┬ ¥
     *      ├ a ┬ ¥
     *      │   └ na ┬ ¥
     *      │        └ na¥
     *      ├ banana¥
     *      └ na <span style='color:red'>╤</span> ¥
     *           └ <span style='color:red'>na¥</span>
     * </pre>
     *
     * @param text text to build suffix tree
     * @param sa suffix array for the text
     * @param lcp longest common prefix array for the text
     * @return suffix tree root node
     */
    public static Node buildSuffixTreeFromSA(String text, int[] sa, int[] lcp) {

        logEntering();

        Node root = new Node(text, null, 0);

        Edge edge0 = root.addNewEdge(text.charAt(sa[0]), sa[0]);

        ActivePoint ap = new ActivePoint(edge0);

        logStep(root, text.substring(sa[0]), ap, 0);

        for (int i = 1; i < sa.length; i++) {

            int prevSuffixLen = ap.activeNode.getStringDepth() + ap.activeLength;
            int stepsUp = prevSuffixLen - lcp[i];

            while (stepsUp > ap.activeLength) {
                stepsUp -= ap.activeLength;
                ap = new ActivePoint(ap.activeNode.getParentEdge());
            }

            Edge newEdge = (stepsUp == ap.activeLength) ?
                ap.activeNode.addNewEdge(text.charAt(sa[i]+lcp[i]), sa[i]+lcp[i]) :
                ap.activeNode.edge(ap.activeEdge).split(ap.activeLength - stepsUp, text.charAt(sa[i]+lcp[i]), sa[i] + lcp[i]);

            ap = new ActivePoint(newEdge);

            logStep(root, text.substring(sa[i]), ap, i);
        }

        sortEdges(root);

        logExiting();

        return root;
    }


	
	@Override
	public String toString() {
		return root.toString();
	}
	
	public static void main(String... args) {
        System.out.println("To log detailed steps, set logger's level to FINE or FINEST. To enable logging, add -Djava.util.logging.config.file=logging.properties to JVM option.");
		String text = args[0];

		new SuffixTree(text);
	}

    /**
     * <p>Active Point locates the position in the suffix tree.</p>
     * <pre>
     *     0┬ ¥
     *      ├ a 1┬ ¥
     *      │    └ na 2┬ ¥
     *      │          └ na¥
     *      ├ banana¥
     *      └ na 3┬ ¥
     *            └ na¥
     *
     * ap = (node0, '', 0): pointing to root node
     * ap = (node0, 'b', 3): pointing to the 3rd character of edge banana¥ of root node.
     * ap = (node0, 'n', 2) is the same as (node3, '', 0). The  Ukkonen's algorithm uses the latter so that the ap is ready to add new edge.
     * </pre>
     *
     */
    public static class ActivePoint {
        public Node activeNode;
        public char activeEdge;
        public int activeLength;

        public ActivePoint(Node activeNode, char activeEdge, int activeLength) {
            this.activeNode = activeNode;
            this.activeEdge = activeEdge;
            this.activeLength = activeLength;
        }

        public ActivePoint(Edge edge) {
            this.activeNode = edge.parentNode;
            this.activeEdge = edge.charAt(0);
            this.activeLength = edge.length();
        }

        public boolean exists(char c) {
            return (activeEdge == '\0' && activeNode.containsEdge(c)) ||
                    (activeEdge != '\0' && activeNode.edge(activeEdge).charAt(activeLength) == c);
        }

        /**
         * walkDownTheEdge is used for Ukkonen's algorithm. So basically, after following a suffix link to go to a new
         * node, you certainly find the active point not pointing to a valid position in an edge (i.e. the ap.activeLength ≥ the
         * length of the active edge. So we need to move the active point down the edge to the next nodes.
         * @param i position of the active point in the text
         */
        public void walkDownTheEdge(int i) {
            String text = activeNode.text;
            while (activeEdge != '\0' && activeNode.edge(activeEdge).length() <= activeLength) { // walk down the edge
                activeLength -= activeNode.edge(activeEdge).length();
                activeNode = activeNode.edge(activeEdge).nextNode;
                activeEdge = activeLength == 0 ? '\0' : text.charAt(i-activeLength);
            }

        }
    }
	
	public static class Node {

        private final String text;


        /**
         * parent-child relationships. Use both map and sorted array to speed up look up ($O(1)$ time) and traversal ($O(1)$ time).
         */
		// should use HashMap. The only reason for using LinkedHashMap is for pretty printing purpose
		// (in the order of edge insertion).
		private final Map<Character, Edge> edges = new LinkedHashMap<>();
		private char[] sortedEdges;

		private Node suffixLink;

        private final Edge parentEdge;

        private final int stringDepth;

		public Node(String text, Edge parentEdge, int stringDepth) {
			this.text = text;
            this.stringDepth = stringDepth;
            this.parentEdge = parentEdge;
		}
		
		public Edge edge(char c) {
			return edges.get(c);
		}

        /**
         * Contain edge $c$?
         * @param c character
         * @return if edge contains the chracter
         */
		public boolean containsEdge(char c) {
			return edges.containsKey(c);
		}

        /**
         * Private method so that it's mutable for the algorithm, but immutable from outside.
         * @param c character
         * @param start position to add the new edge
         * @return new edge
         */
		private Edge addNewEdge(char c, int start) {
			Edge newEdge = new Edge(this, start);
			edges.put(c, newEdge);
			return newEdge;
		}

        /**
         * List of edges in the lexical order.
         * @return first characters of the edges
         */
        public Iterable<Character> edges() {
            return Wrappers.makeIterable(sortedEdges);
        }

        /**
         * True if this is the sentinel leaf node.
         * @return true if the node is leaf
         */
        public boolean isLeaf() {
            return edges.isEmpty();
        }

        /**
         * Node children.
         * @return children nodes
         */
        public Iterable<Node> children() {
            if (sortedEdges != null) {
                return Wrappers.makeIterable(Wrappers.makeIterable(sortedEdges), (c)-> edges.get(c).nextNode );
            }
            else {
                return Wrappers.makeIterable(edges.entrySet(), (e) -> e.getValue().nextNode);
            }
        }

        /**
         * The original text.
         * @return text
         */
        public String getText() {
            return text;
        }

        /**
         * Label is the concatenation of the labels of the edges in the path from root to node. This is derived field.
         * @return label for this node
         */
        public String getLabel() {
            return this.parentEdge == null ? "" : this.parentEdge.parentNode.getLabel() + this.parentEdge.getLabel();
        }

        /**
         * The suffix link of a node whose label is aα is another internal node whose label is α.
         * @return suffix link
         */
        public Node getSuffixLink() {
            return suffixLink;
        }

        /**
         * How deep is the node, measured by the number of characters that must be followed from the root to reach it
         * @return depth
         */
        public int getStringDepth() {
            return stringDepth;
        }

        /**
         * Parent edge. Null if this is the root node.
         * @return parent edge
         */
        public Edge getParentEdge() {
            return parentEdge;
        }

        @Override
		public String toString() {
			StringBuilder builder = new StringBuilder();
			
			if (edges.size() > 0) {
				this.toString(0, builder, new ActivePoint(null, '\0', 0), text.length());
			}
			else {
				builder.append("leaf");
			}

			return builder.toString();
		}

        private void toString(int start, StringBuilder builder, ActivePoint ap, int step) {
            Set<Node> linkedNodes = new HashSet<>();

            for (Node n : Traversal.bsf(this, (v) -> v.children(), new HashSet<>() )) {
                if (n.suffixLink != null) linkedNodes.add(n.suffixLink);
            }

            toString(start, builder, new HashSet<>(), linkedNodes, ap, step);
        }
		
		/**
		 * 
		 * @param start
		 * @param builder
		 * @param nodePositions
         * @param ap active point
         * @param step
         *
		 */
		private void toString(int start, StringBuilder builder, Set<Integer> nodePositions,
                              Set<Node> linkedNodes, ActivePoint ap, int step) {

			ArrayList<Edge> edges = new ArrayList<>(this.edges.values());
			
			StringBuilder padding = new StringBuilder();
			for (int i = 0; i < start; i++) {
				padding.append(nodePositions.contains(i) ? '│' : ' ');
			}
            if (this.suffixLink != null || linkedNodes.contains(this)) padding.append(' ');

			for (int i = 0; i < edges.size(); i++) {
				Edge edge = edges.get(i);
				
				String connector;
				if (i == 0) {
                    connector = this.suffixLink != null && linkedNodes.contains(this) ? "↧" :
                            this.suffixLink != null ? "↓" :
                            linkedNodes.contains(this) ? "∘" : "";
                    if (this == ap.activeNode) {
                        connector += edges.size() > 1 ? "╤" : "═";
                    }
                    else {
                        connector += edges.size() > 1 ? "┬" : "─";
                    }
				}
				else {
					builder.append(padding);
					connector = i < edges.size() - 1 ? "├" : "└";
				}
				
				StringBuilder edgeBuilder = new StringBuilder(text.substring(edge.start, Math.max(edge.start, Math.min(edge.end, step + 1))))
					.append(step < text.length() - 1 && edge.end == text.length() ? "?" : "");
				if (this == ap.activeNode && edge(ap.activeEdge) == edge) {
					edgeBuilder.insert(Math.min(ap.activeLength, edgeBuilder.length()), ']');
					edgeBuilder.insert(0, '[');
				}
				if (logger.isLoggable(Level.FINER)) {
					edgeBuilder.append('[').append(edge.start).append(']');
				}
				builder.append(connector).append(' ').append(edgeBuilder).append(' ');
				if (edge.nextNode.isLeaf()) {
                    builder.setCharAt(builder.length() - 1, '\n');
				}
				else {
                    int thisNodePosition = (this.suffixLink != null || linkedNodes.contains(this) ? 1 : 0) + start;
                    if (i != edges.size() - 1) nodePositions.add(thisNodePosition); // add this for the child to draw the connector.
                    edge.nextNode.toString(thisNodePosition + edgeBuilder.length() + 3, builder, nodePositions, linkedNodes, ap, step);
                    nodePositions.remove(thisNodePosition);
				}
				
			}
		}

    }
	
	
	public static class Edge {

        private final Node parentNode;
		private int start;
		private int end;
		
		private Node nextNode;
		
		public Edge(Node parentNode, int start) {
			this(parentNode, start, parentNode.text.length(), null);
		}
		
		public Edge(Node parentNode, int start, int end, Node nextNode) {
            this.parentNode = parentNode;
			this.start = start;
			this.end = end;
            if (nextNode == null)  { // add sentinel leaf node.
                nextNode = new Node(parentNode.text, this, parentNode.stringDepth + (end-start));
            }
			this.nextNode = nextNode;

		}
		
		public char charAt(int pos) {
			if (pos < 0 || pos >= (end - start)) {
				throw new IndexOutOfBoundsException();
			}
			return parentNode.text.charAt(start + pos);
		}
		
		public int length() {
			return end - start;
		}
		
		public Edge split(int pos, char newchar, int newcharStart) {
			if (pos <= 0 || pos >= (end - start)) {
				throw new IllegalStateException();
			}
			
			int splitPos = pos + start;
			
			Node newNode = new Node(parentNode.text, this, parentNode.stringDepth + pos);
			newNode.edges.put(parentNode.text.charAt(splitPos), new Edge(newNode, splitPos, end, nextNode));
            Edge newEdge = new Edge(newNode, newcharStart);
			newNode.edges.put(newchar, newEdge);
			
			nextNode = newNode;
			end = splitPos;

            return newEdge;
		}


        public Node getParentNode() {
            return parentNode;
        }

        public int getStart() {
            return start;
        }

        public int getEnd() {
            return end;
        }

        public Node getNextNode() {
            return nextNode;
        }

        /**
         * Derived field.
         * @return label for this edge
         */
        public String getLabel() {
            return parentNode.text.substring(start, end);
        }

        @Override
		public String toString() {
			return parentNode.text.substring(start, end);
		}

    }

















    public static class Operations {

        public static ActivePoint find(Node tree, String pattern) {

            ActivePoint ap = new ActivePoint(tree, '\0', 0);

            for (int i = 0; i < pattern.length(); i++) {
                char c = pattern.charAt(i);

                if (!ap.exists(c)) return null;

                if (ap.activeEdge == '\0') ap.activeEdge = c;
                ap.activeLength++;
                ap.walkDownTheEdge(i);
                if (ap.activeNode == null) return null;
            }

            return ap;
        }






    }

}
